package _0796_Rotate_String;

/**
 * Date: 2021/10/2 11:35
 * Content:
 */
public class Solution {

    public boolean rotateString(String A, String B) {
        if (A.length() != B.length()) return false;
        return get_min(A).equals(get_min(B));
    }

    private String get_min(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        sb.append(s).append(s);
        char[] cs = sb.toString().toCharArray();
        int i = 0, j = 1;
        while (i < n && j < n) {
            int k = 0;
            while (k < n && cs[i + k] == cs[j + k]) k++;
            if (cs[i + k] > cs[j + k]) i += k + 1;
            else j += k + 1;

            if (i == j) i++;
        }
        int k = Math.min(i, j);
        return sb.substring(k, k + n);
    }

    public static void main(String[] args) {

        System.out.println((new Solution()).rotateString("abcde", "cdeab"));  // true
    }
}
